package com.lwl.Algorithmic_data_structure.滑动窗口;

import org.junit.Test;

import java.util.LinkedList;

public class 小于num的子数组数量 {
    @Test
    public void test(){
        System.out.println(AllLessNumSubArray(new int[]{10, 20, 30, 40}, 5));
    }

    public static int AllLessNumSubArray(int[] arr,int num){
        if (arr == null || arr.length == 0 || num < 0){
            return 0;
        }
        LinkedList<Integer> minList = new LinkedList<>();
        LinkedList<Integer> maxList = new LinkedList<>();
        int R = 0;
        int res = 0;
        for (int L = 0; L < arr.length; L++) {
            //L是不可能走到R 的 前面的 因为相等的时候 之差为 0 R肯定会继续向右移动的
            while (R < arr.length){
                while (!maxList.isEmpty() && arr[R] >= arr[maxList.peekLast()]){
                    maxList.pollLast();
                }
                maxList.addLast(R);
                while (!minList.isEmpty() && arr[R] <= arr[minList.peekLast()]){
                    minList.pollLast();
                }
                minList.addLast(R);
                //比较当前窗口的最大值 和 最小值 的差
                if (arr[maxList.peekFirst()] - arr[minList.peekFirst()] <= num){
                    R++;
                }else{
                    break;
                }
            }
            //现在 [L,R] 这个闭区间是不满足条件了,但是[L,R) 还是满足的
            // 一次性加上以L 为 起始点 在[L,R)中的子数组数量
            res += R - L;
            //L 马上就要 ++l，所以要判断剔除的L是不是最大值，或者最小值，及时更新
            if (L == minList.peekFirst()){
                minList.pollFirst();
            }
            if (L == maxList.peekFirst()){
                maxList.pollFirst();
            }
        }
        return res;
    }
}
